#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include <stdio.h>
#include <string.h>

using namespace std;


class Trie
{
public:
    Trie(){
        isEnd = false;
        memset(children, 0, 26*sizeof(Trie *));
    }

    void insert(const char *str)
    {
        Trie *dict = this;
        while(*str) {
            int index = *str - 'a';
            if (!dict->children[index]) {
                dict->children[index] = new Trie();
            }
            dict = dict->children[index];
            str++;
        }
        dict->isEnd = true;
    }

    bool isEnd;
    Trie *children[26];
};

int X[] = {0, -1, 0, 1, -1, -1, 1, 1};
int Y[] = {1, 0, -1, 0, -1, 1, -1, 1};
void findWord(string str[], int i, int j, int m, int n, Trie *dict, string cur, set<string> &ans, vector<vector<bool> > &visited)
{
    if (i < 0 || i >= m || j < 0 || j >= n) 
        return;
    if (visited[i][j]) return;
  
    char ch = str[i][j];
    if (!dict->children[ch-'a'])
        return;

    visited[i][j] = true;  
    cur += ch;
    dict = dict->children[ch-'a'];
    if (dict->isEnd) {
        ans.insert(cur);    
    }

    for (int k = 0; k < 8; k++) 
        findWord(str, i+X[k], j+Y[k], m, n, dict, cur, ans, visited);
    visited[i][j] = false;  
}


set<string> findBoggle(string str[], int m, int n, Trie *dict)
{
    vector<vector<bool> > visited(m, vector<bool>(n, false));
    set<string> ans;
    string cur;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            findWord(str, i, j, m, n, dict, cur, ans, visited);
        }
    }
    return ans;
}

int main(int argc, char **argv)
{
    Trie *dict = new Trie();
    string str[] = {"aelenche",
             "sdfcsdec",
             "decbecez",
             "poevndqc",
             "ceetcbwe",
             "qdcurcec",
             "mndswece",
             "poqwecec"};

    string word[] = {"kkjdkjf",
                    "adeevecs",
                    "ec",
                    "nsencr",
                    "pncteec"};

    for (int i = 0; i < sizeof(word)/sizeof(char*); i++)
        dict->insert(word[i].c_str());

    set<string> result = findBoggle(str, 8, 8, dict);
    for (set<string>::iterator iter = result.begin(); iter != result.end(); iter++)
    {
        cout << *iter << endl;
    }

}
